/* 516. 最长回文子序列 */
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
	const n = s.length
	/* dp[i][j] 字符串i => j的最长回文子序列个数 */
	const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
	for (let i = n - 1; i >= 0; i--) {
		dp[i][i] = 1
		const c1 = s[i]
		for (let j = i + 1; j < n; j++) {
			const c2 = s[j]
			/* 如果首尾相等,取中间的的 + 2 */
			if (c1 === c2) {
				dp[i][j] = dp[i + 1][j - 1] + 2
			} else {
				/* 否则取Math.max(首=> 倒数第二个, 第二个 => 尾) */
				dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
			}
		}
	}

	return dp[0][n - 1]
}
